{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #两数相加 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #linked-list #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #链表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: addTwoNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两数相加 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个 <strong>非空链表</strong> <code>l1</code>和 <code>l2</code>&nbsp;来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。</p>\n",
    "\n",
    "<p>可以假设除了数字 0 之外，这两个数字都不会以零开头。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626420025-fZfzMX-image.png\" style=\"width: 302px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [7,2,4,3], l2 = [5,6,4]\n",
    "<strong>输出：</strong>[7,8,0,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [2,4,3], l2 = [5,6,4]\n",
    "<strong>输出：</strong>[8,0,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [0], l2 = [0]\n",
    "<strong>输出：</strong>[0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表的长度范围为<code> [1, 100]</code></li>\n",
    "\t<li><code>0 &lt;= node.val &lt;= 9</code></li>\n",
    "\t<li>输入数据保证链表代表的数字无前导 0</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 445&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/add-two-numbers-ii/\">https://leetcode-cn.com/problems/add-two-numbers-ii/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [lMSNwu](https://leetcode.cn/problems/lMSNwu/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [lMSNwu](https://leetcode.cn/problems/lMSNwu/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,2,4,3]\\n[5,6,4]', '[2,4,3]\\n[5,6,4]', '[0]\\n[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        rev_l1 = self.reverseList(l1)\n",
    "        rev_l2 = self.reverseList(l2)\n",
    "        count = 0\n",
    "        ret = ListNode()\n",
    "        tmo = ret\n",
    "        while rev_l1 or rev_l2 or count:\n",
    "            num = 0\n",
    "            if rev_l1:\n",
    "                num += rev_l1.val\n",
    "                rev_l1 = rev_l1.next\n",
    "            if rev_l2:\n",
    "                num += rev_l2.val\n",
    "                rev_l2 = rev_l2.next\n",
    "            count, num = divmod(count + num, 10)\n",
    "            tmo.next = ListNode(num)\n",
    "            tmo = tmo.next\n",
    "        return self.reverseList(ret.next)\n",
    "    \n",
    "\n",
    "    def reverseList(self, head):\n",
    "        pre, cur = None, head\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        return pre\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "\n",
    "        def push_into_stack(lst, stc) :\n",
    "            while lst :\n",
    "                stc.append(lst.val)\n",
    "                lst = lst.next\n",
    "\n",
    "        push_into_stack(l1, stack1)\n",
    "        push_into_stack(l2, stack2)\n",
    "\n",
    "        add = 0\n",
    "        next = None\n",
    "        while len(stack1) and len(stack2) :\n",
    "            sum = stack1.pop() + stack2.pop() + add\n",
    "            cur = ListNode(sum%10, next)\n",
    "            next = cur\n",
    "            add = int(sum / 10)\n",
    "\n",
    "        while len(stack1) :\n",
    "            sum = stack1.pop() + add\n",
    "            cur = ListNode(sum%10, next)\n",
    "            next = cur\n",
    "            add = int(sum / 10)\n",
    "\n",
    "        while len(stack2) :\n",
    "            sum = stack2.pop() + add\n",
    "            cur = ListNode(sum%10, next)\n",
    "            next = cur\n",
    "            add = int(sum / 10)\n",
    "        \n",
    "        if add :\n",
    "            cur = ListNode(add, next)\n",
    "            next = cur\n",
    "        \n",
    "        return next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        pre, cur = None, head\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre, cur = cur, tmp\n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        rev_l1 = self.reverseList(l1)\n",
    "        rev_l2 = self.reverseList(l2)\n",
    "        count = 0\n",
    "        ret = ListNode()\n",
    "        tmp = ret\n",
    "        while rev_l1 or rev_l2 or count:\n",
    "            num = 0\n",
    "            if rev_l1:\n",
    "                num += rev_l1.val\n",
    "                rev_l1 = rev_l1.next\n",
    "            if rev_l2:\n",
    "                num += rev_l2.val\n",
    "                rev_l2 = rev_l2.next\n",
    "            count, num = divmod(num + count, 10)\n",
    "            tmp.next = ListNode(num)\n",
    "            tmp = tmp.next\n",
    "        return self.reverseList(ret.next)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        # 第1步：将2个链表变成2个字符串\n",
    "        str1, str2 = '', ''\n",
    "        p1, p2 = l1, l2\n",
    "        while p1:\n",
    "            str1 += str(p1.val)\n",
    "            p1 = p1.next\n",
    "        while p2:\n",
    "            str2 += str(p2.val)\n",
    "            p2 = p2.next\n",
    "        \n",
    "        # 第2步：将2个字符串变成数字，相加\n",
    "        str3 = str(eval(''.join([str1, '+', str2])))\n",
    "        # str3 = str(int(str1) + int(str2))\n",
    "        \n",
    "        # 第3步：将结果变成链表\n",
    "        pre = None\n",
    "        for i in range(len(str3) - 1, -1, -1):\n",
    "            curnode = ListNode(int(str3[i]))\n",
    "            curnode.next = pre\n",
    "            pre = curnode\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        r1 = self.reverseList(l1)\n",
    "        r2 = self.reverseList(l2)\n",
    "        flag = False\n",
    "        prev = ListNode()\n",
    "        ans = prev\n",
    "        while r1 or r2:\n",
    "            if not r1:\n",
    "                r1 = ListNode(0)\n",
    "            if not r2:\n",
    "                r2 = ListNode(0)\n",
    "            temp = r1.val + r2.val + (1 if flag else 0)\n",
    "            flag = temp >= 10\n",
    "            prev.val = temp % 10 if temp >= 10 else temp\n",
    "            r1 = r1.next\n",
    "            r2 = r2.next\n",
    "            prev.next = ListNode()\n",
    "            if not r1 and not r2:\n",
    "                if not flag:\n",
    "                    prev.next = None\n",
    "                else:\n",
    "                    prev.next.val = 1\n",
    "            else:\n",
    "                prev = prev.next\n",
    "        reversed = self.reverseList(ans)\n",
    "        return reversed\n",
    "\n",
    "\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ans = None\n",
    "        current = head\n",
    "        while current:\n",
    "            temp = current.next\n",
    "            current.next = ans\n",
    "            ans = current\n",
    "            current = temp\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def rev(head):\n",
    "            pre = None\n",
    "            cur = head\n",
    "            while cur:\n",
    "                tmp = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = tmp\n",
    "            return pre\n",
    "        l1 = rev(l1)\n",
    "        l2 = rev(l2)\n",
    "        carry = 0\n",
    "        res = ListNode()\n",
    "        cur = res\n",
    "        while l1 or l2 or carry:\n",
    "            tmp = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            carry = tmp // 10\n",
    "            res.val = tmp % 10\n",
    "            if l1:\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                l2 = l2.next\n",
    "            if l1 or l2 or carry:\n",
    "                res.next = ListNode()\n",
    "                res = res.next\n",
    "        return rev(cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        rs1 = self.getIntFromListNode(l1)\n",
    "        rs2 = self.getIntFromListNode(l2)\n",
    "        rs = str(rs1 + rs2)\n",
    "        loc = len(rs) -1\n",
    "        n = None\n",
    "        while loc >= 0:\n",
    "            n = ListNode(int(rs[loc]), n)\n",
    "            loc -= 1\n",
    "\n",
    "        return n\n",
    "        \n",
    "    def getIntFromListNode(self, l:ListNode)->int:\n",
    "        rs = 0 \n",
    "        calc_node = l\n",
    "        counter = 10\n",
    "        while calc_node.next!=None:\n",
    "            rs = rs*counter + calc_node.val\n",
    "            calc_node = calc_node.next\n",
    "        rs = rs*counter + calc_node.val\n",
    "        return rs\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def reverse(head):\n",
    "            L = 0\n",
    "            pre = None\n",
    "            while head:\n",
    "                L += 1\n",
    "                next = head.next\n",
    "                head.next = pre\n",
    "                pre = head\n",
    "                head = next\n",
    "            return pre, L\n",
    "\n",
    "        l1, N1 = reverse(l1)\n",
    "        l2, N2 = reverse(l2)\n",
    "\n",
    "        l1, l2 = (l1, l2) if N1 < N2 else (l2, l1)\n",
    "        N1, N2 = (N1, N2) if N1 < N2 else (N2, N1)\n",
    "        c = 0\n",
    "        \n",
    "        ans, tail = l2, l2\n",
    "        while l1:\n",
    "            l2.val += l1.val + c\n",
    "            c = 1 if l2.val >= 10 else 0\n",
    "            l2.val = l2.val%10 if l2.val >= 10 else l2.val\n",
    "            tail = l2\n",
    "            l2 = l2.next\n",
    "            l1 = l1.next\n",
    "\n",
    "        while l2:\n",
    "            l2.val += c\n",
    "            c = 1 if l2.val >= 10 else 0\n",
    "            l2.val = l2.val%10 if l2.val >= 10 else l2.val\n",
    "            tail = l2\n",
    "            l2 = l2.next\n",
    "\n",
    "        if c:\n",
    "            tail.next = ListNode(1)\n",
    "        ans, _ = reverse(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        self.stack_1 = []\n",
    "        self.stack_2 = []\n",
    "        self.stack_3 = []\n",
    "        self.get_val(l1, self.stack_1)\n",
    "        self.get_val(l2, self.stack_2)\n",
    "        return self.generate()\n",
    "    \n",
    "    def get_val(self, list_node, stack):\n",
    "        while list_node:\n",
    "            stack.append(list_node.val)\n",
    "            list_node = list_node.next\n",
    "\n",
    "    def generate(self):\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while self.stack_1 or self.stack_2 or carry:\n",
    "            value_1 = 0 if not self.stack_1 else self.stack_1.pop()\n",
    "            value_2 = 0 if not self.stack_2 else self.stack_2.pop()\n",
    "            cur = value_1 + value_2 + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            currnode = ListNode(cur)\n",
    "            currnode.next = ans\n",
    "            ans = currnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        res1 = []\n",
    "        res2 = []\n",
    "        ll1 = l1\n",
    "        ll2 = l2\n",
    "        while ll1 or ll2:\n",
    "            if ll1:\n",
    "                res1.append(str(ll1.val))\n",
    "                ll1 = ll1.next\n",
    "            if ll2:\n",
    "                res2.append(str(ll2.val))\n",
    "                ll2 = ll2.next\n",
    "\n",
    "        res1 = \"\".join(res1)[::-1]\n",
    "        res2 = \"\".join(res2)[::-1]\n",
    "\n",
    "        res = []\n",
    "        len1 = len(res1)\n",
    "        len2 = len(res2)\n",
    "        i = j = 0\n",
    "        carry = 0\n",
    "        while i < len1 or j < len2:\n",
    "            a = int(res1[i]) if i < len1 else 0\n",
    "            b = int(res2[j]) if j < len2 else 0\n",
    "            ans = a + b + carry\n",
    "            carry = ans // 10\n",
    "            res.append(ListNode(ans % 10))\n",
    "            i += 1\n",
    "            j += 1\n",
    "        if carry:\n",
    "            res.append(ListNode(carry))\n",
    "        res = res[::-1]\n",
    "        for i in range(len(res) - 1):\n",
    "            res[i].next = res[i + 1]\n",
    "        return res[0]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        a = b = None\n",
    "        while l1:\n",
    "            l1.next, a, l1 = a, l1, l1.next\n",
    "        while l2:\n",
    "            l2.next, b, l2 = b, l2, l2.next\n",
    "        result, c = None, 0\n",
    "        while a or b or c:\n",
    "            if a:\n",
    "                c, a = c + a.val, a.next\n",
    "            if b:\n",
    "                c, b = c + b.val, b.next\n",
    "            c, result = c // 10, ListNode(c % 10, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        pre, cur = None, head\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre, cur = cur, tmp\n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        rev_l1 = self.reverseList(l1)\n",
    "        rev_l2 = self.reverseList(l2)\n",
    "        count = 0\n",
    "        ret = ListNode()\n",
    "        tmp = ret\n",
    "        while rev_l1 or rev_l2 or count:\n",
    "            num = 0\n",
    "            if rev_l1:\n",
    "                num += rev_l1.val\n",
    "                rev_l1 = rev_l1.next\n",
    "            if rev_l2:\n",
    "                num += rev_l2.val\n",
    "                rev_l2 = rev_l2.next\n",
    "            count, num = divmod(num + count, 10)\n",
    "            tmp.next = ListNode(num)\n",
    "            tmp = tmp.next\n",
    "        return self.reverseList(ret.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        rs1 = self.getIntFromListNode(l1)\n",
    "        rs2 = self.getIntFromListNode(l2)\n",
    "        rs = str(rs1 + rs2)\n",
    "        loc = len(rs) -1\n",
    "        n = None\n",
    "        while loc >= 0:\n",
    "            n = ListNode(int(rs[loc]), n)\n",
    "            loc -= 1\n",
    "\n",
    "        return n\n",
    "        \n",
    "    def getIntFromListNode(self, l:ListNode)->int:\n",
    "        rs = 0 \n",
    "        calc_node = l\n",
    "        counter = 10\n",
    "        while calc_node.next!=None:\n",
    "            rs = rs*counter + calc_node.val\n",
    "            calc_node = calc_node.next\n",
    "        rs = rs*counter + calc_node.val\n",
    "        return rs\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        '''\n",
    "        反转链表 -> 计算 -> 反转链表\n",
    "        '''\n",
    "\n",
    "        def reverse_list(head):\n",
    "            '''翻转链表\n",
    "            '''\n",
    "            if head is None or head.next is None:\n",
    "                return head\n",
    "\n",
    "            slow = head\n",
    "            fast = head.next\n",
    "            while(fast is not None):\n",
    "                tmp = fast.next\n",
    "                fast.next = slow\n",
    "                if slow is head:\n",
    "                    slow.next = None\n",
    "                slow = fast\n",
    "                fast = tmp\n",
    "            return slow\n",
    "\n",
    "        l1 = reverse_list(l1)\n",
    "        l2 = reverse_list(l2)\n",
    "\n",
    "        dummy_head = ListNode()\n",
    "        curr_out = dummy_head\n",
    "        curr1 = l1; curr2 = l2\n",
    "        tmp = 0\n",
    "        while(curr1 is not None or curr2 is not None):\n",
    "            val = 0\n",
    "            if curr1 is not None:\n",
    "                val += curr1.val\n",
    "                curr1 = curr1.next\n",
    "\n",
    "            if curr2 is not None:\n",
    "                val += curr2.val\n",
    "                curr2 = curr2.next\n",
    "\n",
    "            val += tmp\n",
    "            curr_out.next = ListNode(val % 10)\n",
    "            curr_out = curr_out.next\n",
    "            tmp = val // 10\n",
    "\n",
    "        if tmp:\n",
    "            curr_out.next = ListNode(tmp)\n",
    "\n",
    "        rst = dummy_head.next\n",
    "        rst = reverse_list(rst)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry > 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            total = a + b + carry\n",
    "            carry = total // 10\n",
    "            total = total % 10\n",
    "            curnode = ListNode(total)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\"\"\"\n",
    "方法1栈的思维\n",
    "\"\"\"\n",
    "# class Solution:\n",
    "#     def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "#         a = []\n",
    "#         b = []\n",
    "#         while l1:\n",
    "#             a.append(l1.val)\n",
    "#             l1 = l1.next\n",
    "\n",
    "#         while l2:\n",
    "#             b.append(l2.val)\n",
    "#             l2 = l2.next\n",
    "#         r = None\n",
    "#         carry = 0\n",
    "#         while a or b or carry:\n",
    "#             x = a.pop(-1) if a else 0\n",
    "#             y = b.pop(-1) if b else 0\n",
    "#             carry, cur_val = divmod(x+y+carry, 10)\n",
    "\n",
    "#             cur = ListNode(cur_val)\n",
    "#             cur.next = r\n",
    "#             r = cur\n",
    "\n",
    "#         return r\n",
    "\"\"\"\n",
    "方法2反转链表的思维\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        pre = q = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            q = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = q\n",
    "        \n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        r_l1 = self.reverseList(l1)\n",
    "        r_l2 = self.reverseList(l2)\n",
    "        carry = 0\n",
    "        result = None\n",
    "        while r_l1 or r_l2 or carry:\n",
    "            num = 0\n",
    "            if r_l1:\n",
    "                num += r_l1.val\n",
    "                r_l1 = r_l1.next\n",
    "            if r_l2:\n",
    "                num += r_l2.val\n",
    "                r_l2 = r_l2.next\n",
    "            carry, cur_val = divmod(num + carry, 10)\n",
    "            cur_node = ListNode(cur_val)\n",
    "            cur_node.next = result\n",
    "            result = cur_node\n",
    "        return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverse(self,head):\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        last= self.reverse(head.next)\n",
    "        head.next.next=  head\n",
    "        head.next=  None\n",
    "        return last\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reverse(l1)\n",
    "        l2 = self.reverse(l2)\n",
    "        dummy = ListNode(-1)\n",
    "        p = dummy\n",
    "        step = 0\n",
    "        while l1 or l2 or step:\n",
    "            cur = step\n",
    "            if l1:\n",
    "                cur+=l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                cur+=l2.val\n",
    "                l2 = l2.next\n",
    "            step,a = divmod(cur,10)\n",
    "            p.next= ListNode(a,None)\n",
    "            p = p.next\n",
    "        p = self.reverse(dummy.next)\n",
    "        return p \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        num1, num2 = 0, 0\n",
    "        cur = l1\n",
    "        while cur:\n",
    "            num1 = num1 * 10 + cur.val\n",
    "            cur = cur.next\n",
    "        cur = l2\n",
    "        while cur:\n",
    "            num2 = num2 * 10 + cur.val\n",
    "            cur = cur.next\n",
    "        res = num1 + num2\n",
    "        cur = ListNode(res % 10)\n",
    "        res = res // 10\n",
    "        while res:\n",
    "            p = ListNode(res % 10)\n",
    "            res = res // 10\n",
    "            p.next = cur\n",
    "            cur = p\n",
    "        return cur\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1,s2=[],[]\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1=l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans =None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a+b+carry\n",
    "            carry  = cur//10\n",
    "            cur %= 10\n",
    "            node = ListNode(cur)\n",
    "            node.next =ans \n",
    "            ans =node\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stk1, stk2 = [], []\n",
    "        while l1:\n",
    "            stk1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stk2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        last = None\n",
    "        carry = 0\n",
    "        while stk1 or stk2 or carry:\n",
    "            if stk1:\n",
    "                carry += stk1.pop()\n",
    "            if stk2:\n",
    "                carry += stk2.pop()\n",
    "            node = ListNode(carry % 10, last)\n",
    "            last = node\n",
    "            carry //= 10\n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\"\"\"\n",
    "方法1栈的思维\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        a = []\n",
    "        b = []\n",
    "        while l1:\n",
    "            a.append(l1.val)\n",
    "            l1 = l1.next\n",
    "\n",
    "        while l2:\n",
    "            b.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        r = None\n",
    "        carry = 0\n",
    "        while a or b or carry:\n",
    "            x = a.pop(-1) if a else 0\n",
    "            y = b.pop(-1) if b else 0\n",
    "            carry, cur_val = divmod(x+y+carry, 10)\n",
    "\n",
    "            cur = ListNode(cur_val)\n",
    "            cur.next = r\n",
    "            r = cur\n",
    "\n",
    "        return r\n",
    "\"\"\"\n",
    "方法2反转链表的思维\n",
    "\"\"\"\n",
    "# class Solution:\n",
    "#     def reverseList(self, head):\n",
    "#         pre = q = None\n",
    "#         cur = head\n",
    "#         while cur:\n",
    "#             q = cur.next\n",
    "#             cur.next = pre\n",
    "#             pre = cur\n",
    "#             cur = q\n",
    "        \n",
    "#         return pre\n",
    "\n",
    "#     def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "#         r_l1 = self.reverseList(l1)\n",
    "#         r_l2 = self.reverseList(l2)\n",
    "#         carry = 0\n",
    "#         result = None\n",
    "#         while r_l1 or r_l2 or carry:\n",
    "#             num = 0\n",
    "#             if r_l1:\n",
    "#                 num += r_l1.val\n",
    "#                 r_l1 = r_l1.next\n",
    "#             if r_l2:\n",
    "#                 num += r_l2.val\n",
    "#                 r_l2 = r_l2.next\n",
    "#             carry, cur_val = divmod(num + carry, 10)\n",
    "#             cur_node = ListNode(cur_val)\n",
    "#             cur_node.next = result\n",
    "#             result = cur_node\n",
    "#         return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stack1=[]\n",
    "        stack2=[]\n",
    "\n",
    "        tmp=l1\n",
    "        while tmp:\n",
    "            stack1.append(tmp.val)\n",
    "            tmp=tmp.next\n",
    "        tmp=l2\n",
    "        while tmp:\n",
    "            stack2.append(tmp.val)\n",
    "            tmp=tmp.next\n",
    "\n",
    "        num3=0\n",
    "        head=None\n",
    "        while stack1 or stack2:\n",
    "            num1=0\n",
    "            if stack1:\n",
    "                num1=stack1.pop()\n",
    "            num2=0\n",
    "            if stack2:\n",
    "                num2=stack2.pop()\n",
    "            sumv=num1+num2+num3\n",
    "            if sumv>=10:\n",
    "                num3=1\n",
    "            else:\n",
    "                num3=0\n",
    "            \n",
    "            newnode=ListNode(sumv%10,head)\n",
    "            head=newnode\n",
    "        if num3:\n",
    "            newnode=ListNode(num3,head)\n",
    "            head=newnode\n",
    "        return head\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode):\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(str(l1.val))\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(str(l2.val))\n",
    "            l2 = l2.next\n",
    "        n1 = ''.join(s1)\n",
    "        n2 = ''.join(s2)\n",
    "        s = str(int(n1) + int(n2))\n",
    "        res = p = ListNode(0)\n",
    "        for i in s:\n",
    "            p.next = ListNode(int(i))\n",
    "            p = p.next\n",
    "        return res.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)\n",
    "        return self.reverseList(self.addTwoListNum(l1, l2))\n",
    "\n",
    "    def reverseList(self, l):\n",
    "        if not l or not l.next:\n",
    "            return l\n",
    "        prev, curr = None, l\n",
    "        while curr:\n",
    "            curr.next, curr, prev = prev, curr.next, curr\n",
    "        return prev\n",
    "\n",
    "    def addTwoListNum(self, l1, l2):\n",
    "        carry = 0\n",
    "        dummy1, prev1, prev2 = ListNode(), ListNode(), ListNode\n",
    "        dummy1.next, prev1.next, prev2.next = l1, l1, l2\n",
    "        while l1 or l2:\n",
    "            if l1 and l2:\n",
    "                # divmod\n",
    "                carry, l1.val = divmod(l1.val+l2.val+carry, 10)\n",
    "                l1, l2, prev1, prev2 = l1.next, l2.next, l1, l2\n",
    "            elif not l1:\n",
    "                l1, prev1.next = l2, l2\n",
    "                # 注意\n",
    "                l2 = None\n",
    "            else:\n",
    "                carry, l1.val = divmod(l1.val+carry, 10)\n",
    "                l1, prev1 = l1.next, l1\n",
    "        # 注意\n",
    "        if carry:\n",
    "            node = ListNode(carry)\n",
    "            prev1.next = node\n",
    "        return dummy1.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1s = []\n",
    "        l2s = []\n",
    "        tree = l1\n",
    "        while l1:\n",
    "            l1s.append(l1)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            l2s.append(l2)\n",
    "            l2 = l2.next\n",
    "        reminder = 0\n",
    "        while l1s and l2s:\n",
    "            cur1 = l1s.pop()\n",
    "            cur2 = l2s.pop()\n",
    "            cur1.val = cur1.val +cur2.val + reminder\n",
    "            reminder = cur1.val//10\n",
    "            cur1.val = cur1.val%10\n",
    "        while reminder or l1s or l2s:\n",
    "            if not l2s and not l1s:\n",
    "                cur = ListNode(reminder)\n",
    "                cur.next = tree\n",
    "                tree = cur\n",
    "                reminder = 0\n",
    "            elif not l2s:\n",
    "                cur = l1s.pop()\n",
    "                cur.val = cur.val+reminder\n",
    "                reminder = cur.val//10\n",
    "                cur.val = cur.val%10\n",
    "            elif not l1s:\n",
    "                cur = l2s.pop()\n",
    "                cur.val = cur.val+reminder\n",
    "                reminder = cur.val//10\n",
    "                cur.val = cur.val%10 \n",
    "                cur.next = tree\n",
    "                tree = cur\n",
    "        return tree        \n",
    "                \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        # 黄狂俄国非空链表翻转\n",
    "        head1 = self.reverse(l1)\n",
    "        head2 = self.reverse(l2)\n",
    "        # 接下来相加\n",
    "        jinwei = 0\n",
    "        dummy = ListNode(val=-1)\n",
    "        cur = dummy\n",
    "        while head1 or head2:\n",
    "            if head1:\n",
    "                num1 = head1.val\n",
    "                head1 = head1.next\n",
    "            else:\n",
    "                num1 = 0\n",
    "            if head2:\n",
    "                num2 = head2.val\n",
    "                head2 = head2.next\n",
    "            else:\n",
    "                num2 = 0\n",
    "            res_temp = (num1+num2+jinwei)%10\n",
    "            jinwei = (num1+num2+jinwei)//10\n",
    "            cur.next = ListNode(val=res_temp)\n",
    "            cur = cur.next\n",
    "        if jinwei==1:\n",
    "            cur.next = ListNode(val=jinwei)\n",
    "        \n",
    "        # 相加后再翻转\n",
    "        temp = dummy.next\n",
    "        dummy.next = None\n",
    "        res = self.reverse(temp)\n",
    "        return (res)\n",
    "\n",
    "\n",
    "\n",
    "    def reverse(self, node):\n",
    "        prev = None\n",
    "        cur = node\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = prev\n",
    "            prev = cur\n",
    "            cur = nxt\n",
    "        return prev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reversal(l):\n",
    "            cur = l\n",
    "            pre = None\n",
    "            while cur:\n",
    "                t = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = t\n",
    "            return pre\n",
    "        l1 = reversal(l1)\n",
    "        l2 = reversal(l2)\n",
    "        head = ListNode()\n",
    "        p = head\n",
    "        jw = 0\n",
    "        while l1 or l2:\n",
    "            p.next = ListNode((l1.val if l1 else 0) + (l2.val if l2 else 0) + jw)\n",
    "            p = p.next\n",
    "            jw = 0\n",
    "            if p.val >= 10:\n",
    "                p.val %= 10\n",
    "                jw = 1\n",
    "            if l1:\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                l2 = l2.next\n",
    "        if jw:\n",
    "            p.next = ListNode(1)\n",
    "        return reversal(head.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1 = []\n",
    "        s2 = []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry = 0\n",
    "        ans = None\n",
    "        while s1 or s2 or carry:\n",
    "            a = s1.pop() if s1 else 0\n",
    "            b = s2.pop() if s2 else 0\n",
    "            carry = a + b + carry\n",
    "            val = carry % 10\n",
    "            carry = carry // 10\n",
    "            node = ListNode(val)\n",
    "            node.next = ans\n",
    "            ans = node\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "\n",
    "        def reverseList(head:ListNode)->ListNode:\n",
    "            prev = None\n",
    "            cur = head\n",
    "            while cur:\n",
    "                next = cur.next\n",
    "                cur.next =  prev\n",
    "                prev = cur\n",
    "                cur = next \n",
    "            return  prev\n",
    "\n",
    "        head1 = reverseList(l1)\n",
    "        head2 = reverseList(l2)\n",
    "\n",
    "\n",
    "        def addReverseList(head1:ListNode,head2:ListNode)->ListNode:\n",
    "            dumpy =  ListNode(0)\n",
    "            sumNode = dumpy\n",
    "            carray = 0\n",
    "            while  head1 or  head2:\n",
    "                sumNum =   (0 if head1 is None else  head1.val) + (0 if head2 is None else  head2.val) + carray\n",
    "                carray =  sumNum//10\n",
    "                newNode = ListNode(sumNum%10)\n",
    "                sumNode.next = newNode\n",
    "                sumNode = sumNode.next\n",
    "                head1 = None if head1 is None else head1.next\n",
    "                head2 = None if head2 is None else head2.next\n",
    "            \n",
    "            if  carray ==1:\n",
    "                sumNode.next =  ListNode(1)\n",
    "\n",
    "            return dumpy.next\n",
    "\n",
    "        node = addReverseList(head1,head2)\n",
    "        return reverseList(node)\n",
    "        \n",
    " \n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reversed(self, heap: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = heap\n",
    "        while cur:\n",
    "            next = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = next\n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        cur = dummy = ListNode()\n",
    "        carry = 0\n",
    "        l1=self.reversed(l1)\n",
    "        l2=self.reversed(l2)\n",
    "        while l1 or l2 or carry:\n",
    "            carry = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            cur.next = ListNode(carry % 10)\n",
    "            carry = carry // 10\n",
    "            cur = cur.next\n",
    "            if l1: l1 = l1.next\n",
    "            if l2: l2 = l2.next\n",
    "        return self.reversed(dummy.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse_node(head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "            cur = head\n",
    "            prev = None\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                cur.next = prev\n",
    "                prev = cur\n",
    "                cur = nxt\n",
    "            return prev\n",
    "        l1, l2 = reverse_node(l1), reverse_node(l2)\n",
    "        \n",
    "        carry = 0\n",
    "        cur = dummy = ListNode()\n",
    "        while l1 or l2 or carry:\n",
    "            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            cur.next = ListNode(carry % 10)\n",
    "            cur = cur.next\n",
    "            carry //= 10\n",
    "            if l1: l1 = l1.next\n",
    "            if l2: l2 = l2.next\n",
    "        dummy.next = reverse_node(dummy.next)\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "\n",
    "import itertools\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        num1 = []\n",
    "        num2 = []\n",
    "\n",
    "        while l1:\n",
    "            num1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "\n",
    "        while l2:\n",
    "            num2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "\n",
    "        res = [0] * (max(len(num1), len(num2)) + 1)\n",
    "        node = None\n",
    "\n",
    "        for i, (n1, n2) in enumerate(itertools.zip_longest(reversed(num1), reversed(num2), fillvalue=0)):\n",
    "            curr_sum = res[i] + n1 + n2\n",
    "\n",
    "            res[i] = curr_sum % 10\n",
    "            res[i + 1] = curr_sum // 10\n",
    "\n",
    "            curr_node = ListNode(res[i])\n",
    "            curr_node.next = node\n",
    "\n",
    "            node = curr_node\n",
    "\n",
    "        if res[-1]:\n",
    "            curr_node = ListNode(res[-1])\n",
    "            curr_node.next = node\n",
    "\n",
    "            node = curr_node\n",
    "\n",
    "        return node\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry, p = 0, None\n",
    "        while s1 or s2 or carry:\n",
    "            num1 = s1.pop() if s1 else 0\n",
    "            num2 = s2.pop() if s2 else 0\n",
    "            ans = num1 + num2 + carry\n",
    "            carry = ans // 10\n",
    "            ans %= 10\n",
    "            p = ListNode(ans, p)\n",
    "        return p\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if l2 is None or l1 is None:\n",
    "            return l1 if l1 else l2\n",
    "        l1, l2 = self.reverse(l1), self.reverse(l2)\n",
    "        # carry = ListNode(0)\n",
    "        p1, p2 = ListNode(), ListNode()\n",
    "        p1, p2 = l1, l2\n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "        carry = 0\n",
    "        while p1 or p2:\n",
    "            carry += (p1.val if p1 else 0) + (p2.val if p2 else 0)\n",
    "            cur.next = ListNode(carry%10)\n",
    "            carry = carry // 10\n",
    "            cur = cur.next\n",
    "            if(p1): p1 = p1.next\n",
    "            if(p2): p2 = p2.next\n",
    "        if carry:\n",
    "            cur.next = ListNode(carry)\n",
    "        return self.reverse(dummy.next)\n",
    "        \n",
    "    def reverse(self, head):\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        pre, cur, las = ListNode(), ListNode(), ListNode()\n",
    "        pre, cur, las = None, head, head.next\n",
    "        while cur:\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = las\n",
    "            if las: las = las.next\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        a = b = 0\n",
    "        cur1, cur2 = l1, l2\n",
    "        while cur1 or cur2:\n",
    "            if cur1:\n",
    "                a = a*10+cur1.val\n",
    "                cur1 = cur1.next\n",
    "            if cur2:\n",
    "                b = b*10+cur2.val\n",
    "                cur2 = cur2.next\n",
    "        c = a+b\n",
    "        dummy_head = ListNode()\n",
    "        while c:\n",
    "            dummy_head.next = ListNode(c % 10, dummy_head.next)\n",
    "            c //= 10\n",
    "        return dummy_head.next if dummy_head.next else dummy_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        num1, num2 = self.transList2Num(l1), self.transList2Num(l2)\n",
    "\n",
    "        sum_num = num1 + num2\n",
    "\n",
    "        return self.transNum2List(sum_num)\n",
    "    \n",
    "    def transNum2List(self, num):\n",
    "        dummyNode = ListNode(0)\n",
    "\n",
    "        while num or dummyNode.next is None:\n",
    "            mod = num % 10\n",
    "            cur_node = ListNode(mod)\n",
    "            cur_node.next = dummyNode.next\n",
    "            dummyNode.next = cur_node\n",
    "\n",
    "            num = num // 10\n",
    "        \n",
    "        return dummyNode.next\n",
    "\n",
    "    def transList2Num(self, head):\n",
    "        res = 0\n",
    "\n",
    "        while head:\n",
    "            res = res * 10 + head.val\n",
    "            head = head.next\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def list2num(head: ListNode) -> int:\n",
    "            num = 0\n",
    "            node = head\n",
    "            while node != None:\n",
    "                num = num * 10 + node.val\n",
    "                node = node.next\n",
    "            return num\n",
    "        \n",
    "        def num2list(num: int) -> ListNode:\n",
    "            _num = num\n",
    "            last = None\n",
    "            if num != 0:\n",
    "                while _num > 0:\n",
    "                    v = _num % 10\n",
    "                    _num //= 10\n",
    "                    node = ListNode(val=v, next=last)\n",
    "                    last = node\n",
    "            else:\n",
    "                last = ListNode(val=0)\n",
    "            return last\n",
    "        \n",
    "        num = list2num(l1)\n",
    "        num += list2num(l2)\n",
    "        node = num2list(num)\n",
    "\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        list1=[]\n",
    "        list2=[]\n",
    "        while l1 or l2:\n",
    "            if l1:\n",
    "                list1.append(l1.val)\n",
    "                l1=l1.next\n",
    "            if l2:\n",
    "                list2.append(l2.val)\n",
    "                l2=l2.next\n",
    "        flag=0\n",
    "        dummy=ListNode()\n",
    "        while list1 or list2:\n",
    "            num1=list1.pop() if list1 else 0\n",
    "            num2=list2.pop() if list2 else 0\n",
    "            cnt=(num1+num2+flag)%10\n",
    "            flag=(num1+num2+flag)//10\n",
    "            p=ListNode(cnt)\n",
    "            p.next=dummy.next\n",
    "            dummy.next=p\n",
    "        if flag==1:\n",
    "            p=ListNode(1)\n",
    "            p.next=dummy.next\n",
    "            dummy.next=p\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:       \n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reverseListNode(l1)\n",
    "        l2 = self.reverseListNode(l2)\n",
    "\n",
    "        dummy_head = ListNode()\n",
    "        cur = dummy_head\n",
    "        carry = 0\n",
    "        while l1 or l2:\n",
    "            val1 = l1.val if l1 else 0\n",
    "            val2 = l2.val if l2 else 0\n",
    "            tmp = val1+val2+carry\n",
    "            cur.next = ListNode(tmp%10)\n",
    "            carry = tmp//10\n",
    "\n",
    "            l1 = l1.next if l1 else l1\n",
    "            l2 = l2.next if l2 else l2\n",
    "            cur = cur.next\n",
    "        \n",
    "        if carry:\n",
    "            cur.next = ListNode(carry)\n",
    "        \n",
    "        return self.reverseListNode(dummy_head.next) \n",
    "\n",
    "\n",
    "    def reverseListNode(self, l:ListNode):\n",
    "        if not l:\n",
    "            return l\n",
    "        pre, cur = None, l\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "    \n",
    "        return pre\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        rs1 = self.getIntFromListNode(l1)\n",
    "        rs2 = self.getIntFromListNode(l2)\n",
    "        print(rs2)\n",
    "        carry = 0\n",
    "        n = None\n",
    "        while len(rs1) > 0 and len(rs2) > 0:\n",
    "            a = rs1.pop()\n",
    "            b = rs2.pop()\n",
    "            s = a + b + carry\n",
    "            if s >= 10:\n",
    "                s = s% 10\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "            n = ListNode(val=s, next=n)\n",
    "        while len(rs1) > 0:\n",
    "            a = rs1.pop()\n",
    "            s = a+carry\n",
    "            if s >= 10:\n",
    "                s = s% 10\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "            n = ListNode(val=s, next=n)\n",
    "        while len(rs2) > 0:\n",
    "            a = rs2.pop()\n",
    "            s = a+carry\n",
    "            if s >= 10:\n",
    "                s = s% 10\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "            n = ListNode(val=s, next=n)\n",
    "        if carry == 1:\n",
    "            n = ListNode(val=1, next=n)\n",
    "        return n\n",
    "        \n",
    "    def getIntFromListNode(self, l:ListNode)->list[int]:\n",
    "        rs = []\n",
    "        calc_node = l\n",
    "        while calc_node.next!=None:\n",
    "            rs.append(calc_node.val)\n",
    "            calc_node = calc_node.next\n",
    "        rs.append(calc_node.val)\n",
    "        return rs\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def reverse(head):\n",
    "            cur = head\n",
    "            pre = None\n",
    "            while cur:\n",
    "                nt = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur \n",
    "                cur = nt\n",
    "            return pre\n",
    "        l1 = reverse(l1)\n",
    "        l2 = reverse(l2)\n",
    "        carry = 0\n",
    "        cur = ans = ListNode()\n",
    "        while carry or l1 or l2 :\n",
    "            val = carry + (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            carry,val = divmod(val,10)\n",
    "            cur.next = ListNode(val)\n",
    "            cur = cur.next\n",
    "            l1 = l1.next if l1 else None\n",
    "            l2 = l2.next if l2 else None\n",
    "        return reverse(ans.next)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        a = 0\n",
    "        p = l1\n",
    "        while p:\n",
    "            a = a*10+p.val\n",
    "            p = p.next\n",
    "        b = 0\n",
    "        p = l2\n",
    "        while p:\n",
    "            b = b*10+p.val\n",
    "            p = p.next\n",
    "\n",
    "        c = a + b\n",
    "        nums = []\n",
    "        if c:        \n",
    "            while c:\n",
    "                nums.insert(0,c%10)\n",
    "                c //= 10\n",
    "        else:\n",
    "            nums.append(0)\n",
    "        \n",
    "        ans = ListNode()\n",
    "        p = ans\n",
    "        idx,n= 0,len(nums)\n",
    "        while True:\n",
    "            # print(idx)\n",
    "            p.val = nums[idx]\n",
    "            # ans.insert(0,c%10)\n",
    "            idx += 1\n",
    "            if idx < n:\n",
    "                p.next = ListNode()\n",
    "                p = p.next\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if len(s1) == 0 else s1.pop()\n",
    "            b = 0 if len(s2) == 0 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverselistnode(self,phead):\n",
    "        if phead == None:\n",
    "            return phead\n",
    "        pre,cur = None,phead\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        return pre\n",
    "        \n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if l1 == None:return l2\n",
    "        if l2 == None:return l1\n",
    "        rev_l1 = self.reverselistnode(l1)\n",
    "        rev_l2 = self.reverselistnode(l2)\n",
    "        carry = 0\n",
    "        dummy = ListNode(val = 0)\n",
    "        current = dummy\n",
    "        while rev_l1 or rev_l2 or carry:\n",
    "            val1 = 0 if rev_l1 == None else rev_l1.val\n",
    "            val2 = 0 if rev_l2 == None else rev_l2.val\n",
    "            temp = val1+val2+carry\n",
    "            carry,temp = divmod(temp,10)\n",
    "            current.next = ListNode(temp)\n",
    "            current = current.next\n",
    "            if rev_l1:\n",
    "                rev_l1 = rev_l1.next\n",
    "            if rev_l2:\n",
    "                rev_l2 = rev_l2.next\n",
    "        return self.reverselistnode(dummy.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode):\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(str(l1.val))\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(str(l2.val))\n",
    "            l2 = l2.next\n",
    "        n1 = ''.join(s1)\n",
    "        n2 = ''.join(s2)\n",
    "        s = str(int(n1) + int(n2))\n",
    "        res = p = ListNode(0)\n",
    "        for i in s:\n",
    "            p.next = ListNode(int(i))\n",
    "            p = p.next\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = 0, 0\n",
    "        while l1:\n",
    "            s1 = s1*10 + l1.val\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2 = s2*10 + l2.val\n",
    "            l2 = l2.next\n",
    "        s = s1 + s2\n",
    "        if s == 0:\n",
    "            return ListNode(0)\n",
    "        res = ListNode()\n",
    "        load = res\n",
    "        loads = []\n",
    "        while s >0:\n",
    "            loads.append(s%10)\n",
    "            s //= 10\n",
    "        loads.reverse()\n",
    "        for v in loads:\n",
    "            tmp = ListNode(v)\n",
    "            load.next = tmp\n",
    "            load = tmp\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        nums1 = self.get_nums(l1)\n",
    "        nums2 = self.get_nums(l2)\n",
    "        result = [0] * (max(len(nums1), len(nums2)) + 1)\n",
    "        i1, i2, i3 = len(nums1) - 1, len(nums2) - 1, len(result) - 1\n",
    "        while i1 >= 0 or i2 >= 0:\n",
    "            if i1 >= 0:\n",
    "                result[i3] += nums1[i1]\n",
    "                i1 -= 1\n",
    "            if i2 >= 0:\n",
    "                result[i3] += nums2[i2]\n",
    "                i2 -= 1\n",
    "            i3 -= 1\n",
    "        for i in range(len(result) - 1, 0, -1):\n",
    "            if result[i] >= 10:\n",
    "                result[i - 1] += result[i] // 10\n",
    "                result[i] %= 10\n",
    "        start = 0 if result[0] > 0 else 1\n",
    "        head = ListNode(result[start])\n",
    "        temp = head\n",
    "        for i in range(start + 1, len(result)):\n",
    "            temp.next = ListNode(result[i])\n",
    "            temp = temp.next\n",
    "        return head\n",
    "\n",
    "    def get_nums(self, head: Optional[ListNode]) -> List[int]:\n",
    "        nums = []\n",
    "        temp = head\n",
    "        while temp is not None:\n",
    "            nums.append(temp.val)\n",
    "            temp = temp.next\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry, p = 0, None\n",
    "        while s1 or s2 or carry:\n",
    "            num1 = s1.pop() if s1 else 0\n",
    "            num2 = s2.pop() if s2 else 0\n",
    "            ans = num1 + num2 + carry\n",
    "            carry = ans // 10\n",
    "            ans %= 10\n",
    "            p = ListNode(ans, p)\n",
    "        return p\n",
    "     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse_node(head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "            cur = head\n",
    "            prev = None\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                cur.next = prev\n",
    "                prev = cur\n",
    "                cur = nxt\n",
    "            return prev\n",
    "        l1, l2 = reverse_node(l1), reverse_node(l2)\n",
    "        \n",
    "        carry = 0\n",
    "        cur = dummy = ListNode()\n",
    "        while l1 or l2 or carry:\n",
    "            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            cur.next = ListNode(carry % 10)\n",
    "            cur = cur.next\n",
    "            carry //= 10\n",
    "            if l1: l1 = l1.next\n",
    "            if l2: l2 = l2.next\n",
    "        dummy.next = reverse_node(dummy.next)\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        str1, str2 = '', ''\n",
    "        p1, p2 = l1, l2\n",
    "        while p1:\n",
    "            str1 += str(p1.val)\n",
    "            p1 = p1.next\n",
    "        while p2:\n",
    "            str2 += str(p2.val)\n",
    "            p2 = p2.next\n",
    "        ret = str(int(str1) + int(str2))\n",
    "        pre = None\n",
    "        for i in range(len(ret) - 1, -1, -1):\n",
    "            curnode = ListNode(int(ret[i]))\n",
    "            curnode.next = pre\n",
    "            pre = curnode\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)\n",
    "        return self.reverseList(self.addTwoListNum(l1, l2))\n",
    "\n",
    "    def reverseList(self, l):\n",
    "        if not l or not l.next:\n",
    "            return l\n",
    "        prev, curr = None, l\n",
    "        while curr:\n",
    "            curr.next, curr, prev = prev, curr.next, curr\n",
    "        return prev\n",
    "\n",
    "    def addTwoListNum(self, l1, l2):\n",
    "        carry = 0\n",
    "        dummy1, prev1, prev2 = ListNode(), ListNode(), ListNode\n",
    "        dummy1.next, prev1.next, prev2.next = l1, l1, l2\n",
    "        while l1 or l2:\n",
    "            if l1 and l2:\n",
    "                carry, l1.val = divmod(l1.val+l2.val+carry, 10)\n",
    "                l1, l2, prev1, prev2 = l1.next, l2.next, l1, l2\n",
    "            elif not l1:\n",
    "                l1, prev1.next = l2, l2\n",
    "                l2 = None\n",
    "            else:\n",
    "                carry, l1.val = divmod(l1.val+carry, 10)\n",
    "                l1, prev1 = l1.next, l1\n",
    "        if carry:\n",
    "            node = ListNode(carry)\n",
    "            prev1.next = node\n",
    "        return dummy1.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def func(head):\n",
    "            cur = head\n",
    "            s = ''\n",
    "            while cur:\n",
    "                s += str(cur.val)\n",
    "                cur = cur.next\n",
    "            return s \n",
    "        s1 = func(l1)\n",
    "        s2 = func(l2)\n",
    "        n = str(int(s1)+int(s2))\n",
    "        cur = ans = ListNode()\n",
    "        for i in n:\n",
    "            cur.next = ListNode(int(i))\n",
    "            cur = cur.next\n",
    "        return ans.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def reverse(head) -> ListNode:\n",
    "            pre, cur = None, head\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = nxt\n",
    "            return pre\n",
    "        \n",
    "        def addTwo(l1, l2) -> ListNode:\n",
    "            cur = dummy = ListNode()\n",
    "            carry = 0\n",
    "            while l1 or l2 or carry:\n",
    "                if l1:\n",
    "                    carry += l1.val\n",
    "                    l1 = l1.next\n",
    "                if l2:\n",
    "                    carry += l2.val\n",
    "                    l2 = l2.next\n",
    "                cur.next = ListNode(carry % 10)\n",
    "                carry //= 10\n",
    "                cur = cur.next\n",
    "            return dummy.next\n",
    "        l1 = reverse(l1)\n",
    "        l2 = reverse(l2)\n",
    "        l3 = addTwo(l1,l2)\n",
    "        return reverse(l3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "\n",
    "        def tranverse(l):\n",
    "            sum_res = 0\n",
    "\n",
    "            while l is not None:\n",
    "                temp = l.val\n",
    "                sum_res = sum_res * 10 + temp\n",
    "                l = l.next \n",
    "            return sum_res\n",
    "\n",
    "        l1_sum = tranverse(l1)\n",
    "\n",
    "        print(l1_sum)\n",
    "        l2_sum = tranverse(l2)\n",
    "        print(l2_sum)\n",
    "\n",
    "        total_sum = str(l1_sum + l2_sum)\n",
    "        print(total_sum)\n",
    "\n",
    "        pre_head = ListNode()\n",
    "        cur = pre_head\n",
    "\n",
    "        while total_sum:\n",
    "            node = ListNode(int(total_sum[0]))\n",
    "            total_sum = total_sum[1:]\n",
    "            cur.next = node\n",
    "            cur = node\n",
    "\n",
    "        return pre_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        rs1 = self.getIntFromListNode(l1)\n",
    "        rs2 = self.getIntFromListNode(l2)\n",
    "        rs = str(rs1 + rs2)\n",
    "        loc = len(rs) -1\n",
    "        n = None\n",
    "        while loc >= 0:\n",
    "            n = ListNode(int(rs[loc]), n)\n",
    "            loc -= 1\n",
    "\n",
    "        return n\n",
    "        \n",
    "    def getIntFromListNode(self, l:ListNode)->int:\n",
    "        rs = 0 \n",
    "        calc_node = l\n",
    "        counter = 10\n",
    "        while calc_node.next!=None:\n",
    "            rs = rs*counter + calc_node.val\n",
    "            calc_node = calc_node.next\n",
    "        rs = rs*counter + calc_node.val\n",
    "        return rs\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1 and not l2:\n",
    "            return \n",
    "        if not l1:\n",
    "            return l2\n",
    "        if not l2:\n",
    "            return l1\n",
    "        def getNum(l):\n",
    "            num=0\n",
    "            while l:\n",
    "                num=10*num+l.val\n",
    "                l=l.next\n",
    "            return num\n",
    "        num=getNum(l1)+getNum(l2)\n",
    "        print(num)\n",
    "        node=None\n",
    "        for i in str(num)[::-1]:\n",
    "            #print(i)\n",
    "            node=ListNode(int(i),node)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "\n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        carry = 0\n",
    "        dummy = ListNode(-1)\n",
    "        while stack1 or stack2 or carry:\n",
    "            tmp_sum = carry\n",
    "            if stack1:\n",
    "                tmp_sum += stack1.pop()\n",
    "            if stack2:\n",
    "                tmp_sum += stack2.pop()\n",
    "            carry = tmp_sum // 10\n",
    "            node = ListNode(tmp_sum % 10)\n",
    "            node.next = dummy.next\n",
    "            dummy.next = node\n",
    "\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        while l1:\n",
    "            stack1.append(l1)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2)\n",
    "            l2 = l2.next\n",
    "        carry = 0\n",
    "        nxt = None\n",
    "        res = None\n",
    "        while stack1 or stack2:\n",
    "            if stack1:\n",
    "                t1 = stack1.pop().val\n",
    "            else:\n",
    "                t1 = 0\n",
    "            if stack2:\n",
    "                t2 = stack2.pop().val\n",
    "            else:\n",
    "                t2 = 0\n",
    "            res = ListNode((t1 + t2 + carry) % 10)\n",
    "            carry = 1 if (t1 + t2 + carry) >= 10 else 0\n",
    "            res.next = nxt\n",
    "            nxt = res\n",
    "        if carry:\n",
    "            res = ListNode(next=res, val=1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(cur):\n",
    "            pre = None\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = nxt\n",
    "            return pre\n",
    "\n",
    "        l1, l2 = reverse(l1), reverse(l2)\n",
    "        carry = 0\n",
    "        dummy = ListNode(-1)\n",
    "        cur = dummy\n",
    "        while l1 or l2 or carry:\n",
    "            x, y = 0, 0\n",
    "            if l1:\n",
    "                x = l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                y = l2.val\n",
    "                l2 = l2.next\n",
    "            s = x + y + carry\n",
    "            ans = ListNode(s % 10)\n",
    "            cur.next = ans\n",
    "            cur = cur.next\n",
    "            carry = s // 10\n",
    "        return reverse(dummy.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry:\n",
    "            a1 = 0 if not s1 else s1.pop()\n",
    "            b1 = 0 if not s2 else s2.pop()\n",
    "            carry = a1 + b1 + carry\n",
    "            cur = carry % 10\n",
    "            carry //= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1 or l1.val == 0:\n",
    "            return l2\n",
    "        \n",
    "        if not l2 or l2.val == 0:\n",
    "            return l1\n",
    "        \n",
    "        buf1 = []\n",
    "        buf2 = []\n",
    "\n",
    "        m = 0\n",
    "        n = 0\n",
    "\n",
    "        while l1:\n",
    "            buf1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "            m += 1\n",
    "\n",
    "        while l2:\n",
    "            buf2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "            n += 1\n",
    "\n",
    "        if m < n:\n",
    "            buf1 = [0] * (n - m) + buf1\n",
    "        elif m > n:\n",
    "            buf2 = [0] * (m - n) + buf2\n",
    "\n",
    "        print(buf1)\n",
    "        print(buf2)\n",
    "\n",
    "        tmp = buf1.pop() + buf2.pop()\n",
    "        one = False\n",
    "        if tmp >= 10:\n",
    "            tail = ListNode(val=tmp%10)\n",
    "            one = True\n",
    "        else:\n",
    "            tail = ListNode(val=tmp)\n",
    "\n",
    "        for i in range(max(m, n)-1):\n",
    "            tmp = buf1.pop() + buf2.pop()\n",
    "\n",
    "            if one:\n",
    "                tmp += 1\n",
    "                one = False\n",
    "            \n",
    "            if tmp >= 10:\n",
    "                tail = ListNode(tmp%10, tail)\n",
    "                one = True\n",
    "            else:\n",
    "                tail = ListNode(tmp, tail)\n",
    "\n",
    "        if one:\n",
    "            tail = ListNode(1, tail)\n",
    "        \n",
    "        return tail\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    flag = 0\n",
    "    def reserve(self, head:ListNode):\n",
    "        pre, cur, nxt = None, head, head\n",
    "        while cur is not None:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reserve(l1)\n",
    "        l2 = self.reserve(l2)\n",
    "        dummy = ListNode(-1)\n",
    "        head = dummy\n",
    "        while l1 is not None and l2 is not None:\n",
    "            Sum = l1.val + l2.val + self.flag\n",
    "            self.flag = 0\n",
    "            if Sum > 9:\n",
    "                self.flag = 1\n",
    "                Sum = Sum % 10\n",
    "            head.next = ListNode(Sum)\n",
    "            head = head.next\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        if l1 is not None:\n",
    "            while l1 is not None:\n",
    "                Sum = l1.val + self.flag\n",
    "                self.flag = 0\n",
    "                if Sum > 9:\n",
    "                    self.flag = 1\n",
    "                    Sum = Sum % 10\n",
    "                head.next = ListNode(Sum)\n",
    "                head = head.next\n",
    "                l1 = l1.next\n",
    "        elif l2 is not None:\n",
    "            while l2 is not None:\n",
    "                Sum = l2.val + self.flag\n",
    "                self.flag = 0\n",
    "                if Sum > 9:\n",
    "                    self.flag = 1\n",
    "                    Sum = Sum % 10\n",
    "                head.next = ListNode(Sum)\n",
    "                head = head.next\n",
    "                l2 = l2.next\n",
    "\n",
    "        if self.flag == 1:\n",
    "            head.next = ListNode(1)\n",
    "        \n",
    "        return self.reserve(dummy.next) \n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry, p = 0, None\n",
    "        while s1 or s2 or carry:\n",
    "            num1 = s1.pop() if s1 else 0\n",
    "            num2 = s2.pop() if s2 else 0\n",
    "            ans = num1 + num2 + carry\n",
    "            carry = ans // 10\n",
    "            ans %= 10\n",
    "            p = ListNode(ans, p)\n",
    "        return p\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1 = []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        \n",
    "        s2 = []\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        c = 0\n",
    "        ans = None\n",
    "        while s1 or s2 or c != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            val = a + b + c\n",
    "            c = val // 10\n",
    "            val = val % 10\n",
    "            ans = ListNode(val, ans)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    # 通过栈来解决\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans\n",
    "    \n",
    "    # 递归解决，不过也需要调用栈，而且python递归成本很高\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoAligned(self, l1, l2):\n",
    "        if l1.next is None and l2.next is None:\n",
    "            sum_val = l1.val + l2.val\n",
    "            res = sum_val//10\n",
    "            val = sum_val%10\n",
    "            return res, ListNode(val, None)\n",
    "        \n",
    "        res, return_node = self.addTwoAligned(l1.next, l2.next)\n",
    "        sum_val = l1.val + l2.val + res\n",
    "        res = sum_val//10\n",
    "        val = sum_val%10\n",
    "\n",
    "        return res, ListNode(val, return_node)\n",
    "\n",
    "    def recursive_add(self, node, end_node, res):\n",
    "        \n",
    "        if node == end_node:\n",
    "            sum_val = node.val + res\n",
    "            new_res = sum_val//10\n",
    "            val = sum_val%10\n",
    "            return new_res, ListNode(val, node.next)\n",
    "        \n",
    "        new_res, new_node = self.recursive_add(node.next, end_node, res)\n",
    "        sum_val = node.val + new_res\n",
    "        new_res = sum_val//10\n",
    "        val = sum_val%10\n",
    "\n",
    "        return new_res, ListNode(val, new_node)\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        temp1 = l1\n",
    "        temp2 = l2\n",
    "\n",
    "        length1 = 0\n",
    "        while(temp1 is not None):\n",
    "            temp1 = temp1.next\n",
    "            length1 += 1\n",
    "        length2 = 0\n",
    "        while(temp2 is not None):\n",
    "            temp2 = temp2.next\n",
    "            length2 += 1\n",
    "        \n",
    "        if length1 < length2:\n",
    "            length1, length2 = length2, length1\n",
    "            l1, l2 = l2, l1\n",
    "        \n",
    "        diff_len = length1 - length2\n",
    "\n",
    "        add_head_1 = l1\n",
    "        while(diff_len>0):\n",
    "            add_head_1 = add_head_1.next\n",
    "            diff_len-=1\n",
    "\n",
    "        res, out_head = self.addTwoAligned(add_head_1, l2)\n",
    "\n",
    "        diff_len = length1 - length2\n",
    "\n",
    "        if diff_len == 0:\n",
    "            if res == 0:\n",
    "                return out_head\n",
    "            else:\n",
    "                new_head = ListNode(1, out_head)\n",
    "                return new_head\n",
    "        else:\n",
    "            diff_len = length1 - length2 - 1\n",
    "            add_head_1 = l1\n",
    "            while(diff_len>0):\n",
    "                add_head_1 = add_head_1.next\n",
    "                diff_len-=1\n",
    "            add_head_1.next = out_head\n",
    "\n",
    "            res, out_head = self.recursive_add(l1, add_head_1, res)\n",
    "\n",
    "\n",
    "            if res == 0:\n",
    "                return out_head\n",
    "            else:\n",
    "                new_head = ListNode(1, out_head)\n",
    "                return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        st1, st2 = [], []\n",
    "        dummy = ListNode()\n",
    "        cur = l1\n",
    "        while cur is not None:\n",
    "            st1.append(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = l2\n",
    "        while cur is not None:\n",
    "            st2.append(cur.val)\n",
    "            cur = cur.next\n",
    "        \n",
    "        carry = 0\n",
    "        while len(st1) != 0 and len(st2) != 0:\n",
    "            # 各取一个数字相加\n",
    "            _sum = st1[-1] + st2[-1] + carry\n",
    "            st1.pop()\n",
    "            st2.pop()\n",
    "            carry = _sum // 10\n",
    "            # 头插法\n",
    "            dummy.next = ListNode(val=_sum%10, next=dummy.next)\n",
    "        \n",
    "        # 将较长链表的剩余部分进行头插\n",
    "        for st in [st1, st2]:\n",
    "            while len(st) != 0:\n",
    "                _sum = st[-1] + carry\n",
    "                st.pop()\n",
    "                carry = _sum // 10\n",
    "                dummy.next = ListNode(val=_sum%10, next=dummy.next)\n",
    "        \n",
    "        # 最终进位\n",
    "        if carry == 1:\n",
    "            dummy.next = ListNode(val=1, next=dummy.next)\n",
    "        \n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "\n",
    "    def reverse(self, head):\n",
    "        if not head: return\n",
    "        cur = head\n",
    "        pre = None\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reverse(l1)\n",
    "        l2 = self.reverse(l2)\n",
    "        next1 = 0\n",
    "        pre = None\n",
    "        cur = ListNode(0)\n",
    "\n",
    "        while l1 and l2:\n",
    "            cur_sum = (l1.val + l2.val + next1)\n",
    "            cur = ListNode(cur_sum % 10)\n",
    "            next1 = cur_sum // 10\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        \n",
    "        while l1:\n",
    "            cur_sum = l1.val + next1\n",
    "            next1 = cur_sum // 10\n",
    "            cur = ListNode(cur_sum % 10)\n",
    "            l1 = l1.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "        \n",
    "        while l2:\n",
    "            cur_sum = l2.val + next1\n",
    "            next1 = cur_sum // 10\n",
    "            cur = ListNode(cur_sum % 10)\n",
    "            l2 = l2.next\n",
    "            cur.next = pre\n",
    "            pre = cur  \n",
    "\n",
    "        if next1:\n",
    "            cur = ListNode(next1)\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "        \n",
    "        return pre\n",
    "\n",
    "\n",
    "\n",
    "    # def reverse(self, head):\n",
    "    #     if not head: return head\n",
    "    #     pre = None\n",
    "    #     cur = head\n",
    "    #     while cur:\n",
    "    #         nxt = cur.next\n",
    "    #         cur.next = pre\n",
    "    #         pre = cur\n",
    "    #         cur = nxt\n",
    "    #     return pre\n",
    "\n",
    "    # def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        \n",
    "\n",
    "        # l1 = self.reverse(l1)\n",
    "        # l2 = self.reverse(l2)\n",
    "        # last = None\n",
    "        \n",
    "        # dummy = ListNode(0)\n",
    "        # cur = dummy\n",
    "        # nxt = 0\n",
    "        # while l1 and l2:\n",
    "        #     cur_sum = l1.val + l2.val + nxt\n",
    "        #     nxt = cur_sum // 10\n",
    "        #     cur = ListNode(cur_sum % 10)\n",
    "        #     l1 = l1.next\n",
    "        #     l2 = l2.next\n",
    "        #     cur.next = last\n",
    "        #     last = cur\n",
    "        \n",
    "        # while l1:\n",
    "        #     cur_sum = l1.val + nxt\n",
    "        #     nxt = cur_sum // 10\n",
    "        #     cur = ListNode(cur_sum % 10)\n",
    "        #     l1 = l1.next\n",
    "        #     cur.next = last\n",
    "        #     last = cur\n",
    "        \n",
    "        # while l2:\n",
    "        #     cur_sum = l2.val + nxt\n",
    "        #     nxt = cur_sum // 10\n",
    "        #     cur = ListNode(cur_sum % 10)\n",
    "        #     l2 = l2.next\n",
    "        #     cur.next = last\n",
    "        #     last = cur  \n",
    "        # if nxt:\n",
    "        #     cur = ListNode(nxt)\n",
    "        #     cur.next = last\n",
    "        #     last = cur\n",
    "        \n",
    "        # return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def rev(head):\n",
    "            pre = None\n",
    "            cur = head\n",
    "            while cur:\n",
    "                tmp = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = tmp\n",
    "            return pre\n",
    "        l1 = rev(l1)\n",
    "        l2 = rev(l2)\n",
    "        carry = 0\n",
    "        res = ListNode(0)\n",
    "        cur = res\n",
    "        while l1 or l2 or carry:\n",
    "            tmp = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            res.val = tmp % 10\n",
    "            carry = tmp // 10\n",
    "            if l1:\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                l2 = l2.next\n",
    "            if l1 or l2 or carry:\n",
    "                res.next = ListNode(0)\n",
    "                res = res.next\n",
    "        print(cur)\n",
    "        cur = rev(cur)\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# class Solution:\n",
    "    # 翻转链表法\n",
    "    # def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "    #     def reverse(head: ListNode):\n",
    "    #         pre, cur = None, head\n",
    "    #         while cur:\n",
    "    #             nxt = cur.next\n",
    "    #             cur.next = pre\n",
    "    #             pre = cur\n",
    "    #             cur = nxt\n",
    "    #         return pre\n",
    "    #     carry = 0 # 保存进位\n",
    "    #     l1 = reverse(l1)\n",
    "    #     l2 = reverse(l2)\n",
    "    #     dummy = cur = ListNode()\n",
    "    #     while l1 or l2 or carry:\n",
    "    #         sum = carry\n",
    "    #         if l1:\n",
    "    #             sum += l1.val\n",
    "    #             l1 = l1.next\n",
    "    #         if l2:\n",
    "    #             sum += l2.val\n",
    "    #             l2 = l2.next\n",
    "    #         carry = sum // 10\n",
    "    #         sum %= 10\n",
    "    #         cur.next = ListNode(val = sum)\n",
    "    #         cur = cur.next\n",
    "    #     return reverse(dummy.next)\n",
    "\n",
    "class Solution:\n",
    "    # 进阶解法\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stack1, stack2 = [], [] # 初始化的时候不能设置为 stack1 = stack2 = [], 否则数据错误\n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        dummy = ListNode()\n",
    "        carry = 0\n",
    "        while stack1 or stack2 or carry:\n",
    "            sum = carry\n",
    "            if stack1:\n",
    "                sum += stack1.pop()\n",
    "            if stack2:\n",
    "                sum += stack2.pop()\n",
    "            carry = sum // 10\n",
    "            # 下面这两步巧妙的将链表顺序调整了\n",
    "            node = ListNode(sum % 10, dummy.next)\n",
    "            dummy.next = node\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def reverse(head: ListNode):\n",
    "            pre, cur = None, head\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = nxt\n",
    "            return pre\n",
    "        carry = 0 # 保存进位\n",
    "        l1 = reverse(l1)\n",
    "        l2 = reverse(l2)\n",
    "        dummy = cur = ListNode()\n",
    "        while l1 or l2 or carry:\n",
    "            sum = carry\n",
    "            if l1:\n",
    "                sum += l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                sum += l2.val\n",
    "                l2 = l2.next\n",
    "            carry = sum // 10\n",
    "            sum %= 10\n",
    "            cur.next = ListNode(val = sum)\n",
    "            cur = cur.next\n",
    "        return reverse(dummy.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def list2num(head: ListNode) -> int:\n",
    "            num = 0\n",
    "            node = head\n",
    "            while node != None:\n",
    "                num = num * 10 + node.val\n",
    "                node = node.next\n",
    "            return num\n",
    "        \n",
    "        def num2list(num: int) -> ListNode:\n",
    "            _num = num\n",
    "            last = None\n",
    "            if num != 0:\n",
    "                while _num > 0:\n",
    "                    v = _num % 10\n",
    "                    _num //= 10\n",
    "                    node = ListNode(val=v, next=last)\n",
    "                    last = node\n",
    "            else:\n",
    "                last = ListNode(val=0)\n",
    "            return last\n",
    "        \n",
    "        num = list2num(l1)\n",
    "        num += list2num(l2)\n",
    "        node = num2list(num)\n",
    "\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        p,q = [],[]\n",
    "        while l1:\n",
    "            p.append(l1)\n",
    "            l1=l1.next\n",
    "        while l2:\n",
    "            q.append(l2)\n",
    "            l2=l2.next\n",
    "        c=0\n",
    "        newHead=None\n",
    "        while len(p) and len(q):\n",
    "            a,b=p.pop(),q.pop()\n",
    "            t=(a.val+b.val+c)%10\n",
    "            c=(a.val+b.val+c)//10\n",
    "            newNode = ListNode(t,newHead)\n",
    "            newHead = newNode\n",
    "        while len(p):\n",
    "            a=p.pop()\n",
    "            t=(a.val+c)%10\n",
    "            c=(a.val+c)//10\n",
    "            newNode = ListNode(t,newHead)\n",
    "            newHead = newNode\n",
    "        while len(q):\n",
    "            b=q.pop()\n",
    "            t=(b.val+c)%10\n",
    "            c=(b.val+c)//10\n",
    "            newNode = ListNode(t,newHead)\n",
    "            newHead = newNode\n",
    "        if c:\n",
    "            newNode = ListNode(c,newHead)\n",
    "            newHead = newNode\n",
    "        return newHead\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        method = 'mine'\n",
    "        if method == 'mine':\n",
    "            list1, list2 = [], []\n",
    "            while l1:\n",
    "                list1.append(l1.val)\n",
    "                l1 = l1.next\n",
    "            while l2:\n",
    "                list2.append(l2.val)\n",
    "                l2 = l2.next\n",
    "            list1 = list1[::-1]\n",
    "            list2 = list2[::-1]\n",
    "            n = max(len(list1), len(list2))\n",
    "            arr = [0] * (n + 1)\n",
    "            for i in range(n):\n",
    "                if i < len(list1):\n",
    "                    arr[i] += list1[i]\n",
    "                if i < len(list2):\n",
    "                    arr[i] += list2[i]\n",
    "                \n",
    "                if arr[i] >= 10:\n",
    "                    arr[i + 1] += 1\n",
    "                    arr[i] -= 10\n",
    "            if arr[-1] == 0: arr.pop()\n",
    "            res = None\n",
    "            for num in arr:\n",
    "                res = ListNode(num, next = res)\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "\n",
    "    def reverse(self, head):\n",
    "        if not head: return\n",
    "        cur = head\n",
    "        pre = None\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reverse(l1)\n",
    "        l2 = self.reverse(l2)\n",
    "        pre = None\n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "        nxt = 0\n",
    "        while l1 and l2:\n",
    "            cur_sum = (l1.val + l2.val + nxt)\n",
    "            cur= ListNode(cur_sum % 10)\n",
    "            nxt = cur_sum // 10\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "        while l1:\n",
    "            cur_sum = (l1.val + nxt)\n",
    "            cur = ListNode(cur_sum % 10)\n",
    "            nxt = cur_sum // 10\n",
    "            l1 = l1.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "        \n",
    "        while l2:\n",
    "            cur_sum = l2.val + nxt\n",
    "            nxt = cur_sum // 10\n",
    "            cur = ListNode(cur_sum % 10)\n",
    "            l2 = l2.next\n",
    "            cur.next = pre\n",
    "            pre = cur  \n",
    "        \n",
    "        if nxt:\n",
    "            cur = ListNode(nxt)\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "        \n",
    "        return cur\n",
    "\n",
    "    # def reverse(self, head):\n",
    "    #     if not head: return head\n",
    "    #     pre = None\n",
    "    #     cur = head\n",
    "    #     while cur:\n",
    "    #         nxt = cur.next\n",
    "    #         cur.next = pre\n",
    "    #         pre = cur\n",
    "    #         cur = nxt\n",
    "    #     return pre\n",
    "\n",
    "    # def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        \n",
    "\n",
    "        # l1 = self.reverse(l1)\n",
    "        # l2 = self.reverse(l2)\n",
    "        # last = None\n",
    "        \n",
    "        # dummy = ListNode(0)\n",
    "        # cur = dummy\n",
    "        # nxt = 0\n",
    "        # while l1 and l2:\n",
    "        #     cur_sum = l1.val + l2.val + nxt\n",
    "        #     nxt = cur_sum // 10\n",
    "        #     cur = ListNode(cur_sum % 10)\n",
    "        #     l1 = l1.next\n",
    "        #     l2 = l2.next\n",
    "        #     cur.next = last\n",
    "        #     last = cur\n",
    "        \n",
    "        # while l1:\n",
    "        #     cur_sum = l1.val + nxt\n",
    "        #     nxt = cur_sum // 10\n",
    "        #     cur = ListNode(cur_sum % 10)\n",
    "        #     l1 = l1.next\n",
    "        #     cur.next = last\n",
    "        #     last = cur\n",
    "        \n",
    "        # while l2:\n",
    "        #     cur_sum = l2.val + nxt\n",
    "        #     nxt = cur_sum // 10\n",
    "        #     cur = ListNode(cur_sum % 10)\n",
    "        #     l2 = l2.next\n",
    "        #     cur.next = last\n",
    "        #     last = cur  \n",
    "        # if nxt:\n",
    "        #     cur = ListNode(nxt)\n",
    "        #     cur.next = last\n",
    "        #     last = cur\n",
    "        \n",
    "        # return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = s1.pop() if s1 else 0\n",
    "            b = s2.pop() if s2 else 0\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
